@inproceedings{chan2018more,
  title={More logarithmic-factor speedups for 3SUM,(median,+)-convolution, and some geometric 3SUM-hard problems},
  author={Chan, Timothy M.},
  booktitle={Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms},
  pages={881--897},
  year={2018},
  organization={SIAM}
}

@article{baran2008subquadratic,
  title={Subquadratic algorithms for 3{SUM}},
  author={Baran, Ilya and Demaine, Erik D and P{\u{a}}tra{\c{s}}cu, Mihai},
  journal={Algorithmica},
  volume={50},
  number={4},
  pages={584--596},
  year={2008},
  publisher={Springer}
}

@inproceedings{han2002sorting,
  title={Sorting integers in ${O}(n \log \log n)$ expected time and linear space},
  author={Han, Y and Thorup, M},
  booktitle={IEEE Symposium on Foundations of Computer Science (FOCS)},
  year={2002}
}

@inproceedings{han2002integer,
  title={Integer sorting in ${O}(n\sqrt{\log \log n})$ expected time and linear space},
  author={Han, Yijie and Thorup, Mikkel},
  booktitle={The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings.},
  pages={135--144},
  year={2002},
  organization={IEEE}
}

@inproceedings{han2002deterministic,
  title={Deterministic sorting in ${O}(n \log \log n)$ time and linear space},
  author={Han, Yijie},
  booktitle={Proceedings of the thiry-fourth annual ACM symposium on Theory of computing},
  pages={602--608},
  year={2002},
  organization={ACM}
}

@article{mirzaian1985selection,
  title={Selection in X+ Y and matrices with sorted rows and columns},
  author={Mirzaian, Andranik and Arjomandi, Eshrat},
  journal={Information processing letters},
  volume={20},
  number={1},
  pages={13--17},
  year={1985},
  publisher={Elsevier}
}

@article{frederickson1993optimal,
  title={An optimal algorithm for selection in a min-heap},
  author={Frederickson, Greg N},
  journal={Information and Computation},
  volume={104},
  number={2},
  pages={197--214},
  year={1993},
  publisher={Elsevier}
}

@inproceedings{Chan2004RefinedUA,
  title={Refined Upper and Lower Bounds for 2-SUM},
  author={AlexanderC. L. Chan and William I. Gasarch and Clyde P. Kruskal},
  year={2004}
}

@article{jin2018simple,
  title={A Simple Near-Linear Pseudopolynomial Time Randomized Algorithm for Subset Sum},
  author={Jin, Ce and Wu, Hongxun},
  journal={arXiv preprint arXiv:1807.11597},
  year={2018}
}

@inproceedings{jin2018simple1,
  title={A Simple Near-Linear Pseudopolynomial Time Randomized Algorithm for Subset Sum},
  author={Jin, Ce and Wu, Hongxun},
  booktitle={2nd Symposium on Simplicity in Algorithms (SOSA 2019)},
  year={2018}
}

@article{pisinger1999linear,
  title={Linear time algorithms for knapsack problems with bounded weights},
  author={Pisinger, David},
  journal={Journal of Algorithms},
  volume={33},
  number={1},
  pages={1--14},
  year={1999},
  publisher={Elsevier}
}

@article{Koiliaris2018Subset,
  title={Subset Sum Made Simple},
  author={Koiliaris, Konstantinos and Xu, Chao},
  year={2018},
}

@inproceedings{koiliaris2017faster,
  title={A faster pseudopolynomial time algorithm for subset sum},
  author={Koiliaris, Konstantinos and Xu, Chao},
  booktitle={Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms},
  pages={1062--1072},
  year={2017},
  organization={SIAM}
}

@article{deleglise1996computing,
  title={Computing pi(x): the Meissel, Lehmer, Lagarias, Miller, Odlyzko method},
  author={Del{\'e}glise, Marc and Rivat, Jo{\"e}l},
  journal={Mathematics of Computation of the American Mathematical Society},
  volume={65},
  number={213},
  pages={235--245},
  year={1996}
}

@article{2015arXiv150301839S,
       author = {{Staple}, Douglas B.},
        title = "{The combinatorial algorithm for computing pi(x)}",
      journal = {arXiv e-prints},
     keywords = {Mathematics - Number Theory, Computer Science - Data Structures and Algorithms, 11N05 (Primary), 11Y16, 11-04 (Secondary)},
         year = "2015",
        month = "Mar",
          eid = {arXiv:1503.01839},
        pages = {arXiv:1503.01839},
archivePrefix = {arXiv},
       eprint = {1503.01839},
 primaryClass = {math.NT},
       adsurl = {https://ui.adsabs.harvard.edu/abs/2015arXiv150301839S},
      adsnote = {Provided by the SAO/NASA Astrophysics Data System}
}

@book{galway2004analytic,
  title={Analytic computation of the prime-counting function},
  author={Galway, William Floyd},
  year={2004},
  publisher={University of Illinois at Urbana-Champaign}
}

@article{lagarias1987computing,
  title={Computing $\pi$ (x): An analytic method},
  author={Lagarias, Jeffrey C and Odlyzko, Andrew M.},
  journal={Journal of Algorithms},
  volume={8},
  number={2},
  pages={173--191},
  year={1987},
  publisher={Elsevier}
}

@incollection{lagarias1984new,
  title={New algorithms for computing $\pi$ (x)},
  author={Lagarias, JC and Odlyzko, AM},
  booktitle={Number theory},
  pages={176--193},
  year={1984},
  publisher={Springer}
}

@article{frederickson1984generalized,
  title={Generalized selection and ranking: sorted matrices},
  author={Frederickson, Greg N and Johnson, Donald B},
  journal={SIAM Journal on computing},
  volume={13},
  number={1},
  pages={14--30},
  year={1984},
  publisher={SIAM}
}

@article{frederickson1990erratum,
  title={Erratum: generalized selection and ranking: sorted matrices},
  author={Frederickson, Greg N and Johnson, Donald B},
  journal={SIAM Journal on Computing},
  volume={19},
  number={1},
  pages={205},
  year={1990},
  publisher={Society for Industrial and Applied Mathematics}
}

@article{frederickson1982complexity,
  title={The complexity of selection and ranking in ${X}+{Y}$ and matrices with sorted columns},
  author={Frederickson, Greg N and Johnson, Donald B},
  journal={Journal of Computer and System Sciences},
  volume={24},
  number={2},
  pages={197--208},
  year={1982},
  publisher={Elsevier}
}

@inproceedings{frederickson1980generalized,
  title={Generalized selection and ranking (Preliminary Version)},
  author={Frederickson, Greg N and Johnson, Donald B},
  booktitle={Proceedings of the twelfth annual ACM symposium on Theory of computing},
  pages={420--428},
  year={1980}
}

@article{pollard1975monte,
  title={A Monte Carlo method for factorization},
  author={Pollard, John M},
  journal={BIT Numerical Mathematics},
  volume={15},
  number={3},
  pages={331--334},
  year={1975},
  publisher={Springer}
}

@article{crochemore2001fast,
  title={A fast and practical bit-vector algorithm for the longest common subsequence problem},
  author={Crochemore, Maxime and Iliopoulos, Costas S and Pinzon, Yoan J and Reid, James F},
  journal={Information Processing Letters},
  volume={80},
  number={6},
  pages={279--285},
  year={2001},
  publisher={Elsevier}
}

@article{masek1980faster,
  title={A faster algorithm computing string edit distances},
  author={Masek, William J and Paterson, Michael S},
  journal={Journal of Computer and System sciences},
  volume={20},
  number={1},
  pages={18--31},
  year={1980},
  publisher={Elsevier}
}

@inproceedings{puatracscu2010possibility,
  title={On the possibility of faster SAT algorithms},
  author={P{\u{a}}tra{\c{s}}cu, Mihai and Williams, Ryan},
  booktitle={Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms},
  pages={1065--1075},
  year={2010},
  organization={SIAM}
}

@article{bentley1980decomposable,
  title={Decomposable searching problems I. Static-to-dynamic transformation},
  author={Bentley, Jon Louis and Saxe, James B},
  journal={Journal of Algorithms},
  volume={1},
  number={4},
  pages={301--358},
  year={1980},
  publisher={Elsevier}
}

@book{Rabin1985Randomized,
  title={Randomized algorithms in number theory},
  author={Rabin, Michael O and Shallit, Jeffery O},
  year={1985},
}

@article{chung2005optimal,
  title={An optimal algorithm for the maximum-density segment problem},
  author={Chung, Kai-min and Lu, Hsueh-I},
  journal={SIAM Journal on Computing},
  volume={34},
  number={2},
  pages={373--387},
  year={2005},
  publisher={SIAM}
}

@article{thorup2007equivalence,
  title={Equivalence between priority queues and sorting},
  author={Thorup, Mikkel},
  journal={Journal of the ACM (JACM)},
  volume={54},
  number={6},
  pages={28},
  year={2007},
  publisher={ACM}
}

@article{misra1982finding,
  title={Finding repeated elements},
  author={Misra, Jayadev and Gries, David},
  journal={Science of computer programming},
  volume={2},
  number={2},
  pages={143--152},
  year={1982},
  publisher={Elsevier}
}

@incollection{boyer1991mjrty,
  title={{MJRTY}-a fast majority vote algorithm},
  author={Boyer, Robert S and Moore, J Strother},
  booktitle={Automated Reasoning},
  pages={105--117},
  year={1991},
  publisher={Springer}
}

@article{fredman1975computing,
  title={On computing the length of longest increasing subsequences},
  author={Fredman, Michael L},
  journal={Discrete Mathematics},
  volume={11},
  number={1},
  pages={29--35},
  year={1975},
  publisher={Elsevier}
}

@article{crochemore2010fast,
  title={Fast computation of a longest increasing subsequence and application},
  author={Crochemore, Maxime and Porat, Ely},
  journal={Information and computation},
  volume={208},
  number={9},
  pages={1054--1059},
  year={2010},
  publisher={Elsevier}
}

@article{gajentaan1995class,
  title={On a class of O (n2) problems in computational geometry},
  author={Gajentaan, Anka and Overmars, Mark H},
  journal={Computational geometry},
  volume={5},
  number={3},
  pages={165--185},
  year={1995},
  publisher={Elsevier}
}

@techreport{brown1977fast,
  title={A Fast Merging Algorithm.},
  author={Brown, Mark R and Tarjan, Robert E},
  year={1977},
  institution={STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE}
}

@book{har2011geometric,
  title={Geometric approximation algorithms},
  author={Har-Peled, Sariel},
  number={173},
  year={2011},
  publisher={American Mathematical Soc.}
}

@article{szemeredi1983extremal,
  title={Extremal problems in discrete geometry},
  author={Szemer{\'e}di, Endre and Trotter, William T.},
  journal={Combinatorica},
  volume={3},
  number={3-4},
  pages={381--392},
  year={1983},
  publisher={Springer}
}

@book{edelsbrunner2012algorithms,
  title={Algorithms in combinatorial geometry},
  author={Edelsbrunner, Herbert},
  volume={10},
  year={2012},
  publisher={Springer Science \& Business Media}
}

@inproceedings{groz2012deterministic,
  title={Deterministic regular expressions in linear time},
  author={Groz, Benot{\^\i}t and Maneth, Sebastian and Staworko, Slawek},
  booktitle={Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database Systems},
  pages={49--60},
  year={2012},
  organization={ACM}
}

@inproceedings{bille2009faster,
  title={Faster regular expression matching},
  author={Bille, Philip and Thorup, Mikkel},
  booktitle={International Colloquium on Automata, Languages, and Programming},
  pages={171--182},
  year={2009},
  organization={Springer}
}

@article{edelsbrunner1986halfplanar,
  title={Halfplanar range search in linear space and O (n0. 695) query time},
  author={Edelsbrunner, Herbert and Welzl, Emo},
  journal={Information Processing Letters},
  volume={23},
  number={5},
  pages={289--293},
  year={1986},
  publisher={Elsevier}
}

@article{patrascu2006logarithmic,
  title={Logarithmic lower bounds in the cell-probe model},
  author={P{\u{a}}tra{\c{s}}cu, Mihai and Demaine, Erik D},
  journal={SIAM Journal on Computing},
  volume={35},
  number={4},
  pages={932--963},
  year={2006},
  publisher={SIAM}
}

@inproceedings{puaatracscu2004tight,
  title={Tight bounds for the partial-sums problem},
  author={P{\u{a}}atra{\c{s}}cu, Mihai and Demaine, Erik D},
  booktitle={Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms},
  pages={20--29},
  year={2004},
  organization={Society for Industrial and Applied Mathematics}
}

@inproceedings{chan2010counting,
  title={Counting inversions, offline orthogonal range counting, and related problems},
  author={Chan, Timothy M. and P{\u{a}}tra{\c{s}}cu, Mihai},
  booktitle={Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms},
  pages={161--173},
  year={2010},
  organization={Society for Industrial and Applied Mathematics}
}

@inproceedings{dietz1989optimal,
  title={Optimal algorithms for list indexing and subset rank},
  author={Dietz, Paul F},
  booktitle={Workshop on Algorithms and Data Structures},
  pages={39--46},
  year={1989},
  organization={Springer}
}

@inproceedings{le2014powers,
  title={Powers of tensors and fast matrix multiplication},
  author={Le Gall, Fran{\c{c}}ois},
  booktitle={Proceedings of the 39th international symposium on symbolic and algebraic computation},
  pages={296--303},
  year={2014},
  organization={ACM}
}

@article{yuster2005fast,
  title={Fast sparse matrix multiplication},
  author={Yuster, Raphael and Zwick, Uri},
  journal={ACM Transactions On Algorithms (TALG)},
  volume={1},
  number={1},
  pages={2--13},
  year={2005},
  publisher={ACM}
}

@inproceedings{le2012faster,
  title={Faster algorithms for rectangular matrix multiplication},
  author={Le Gall, Fran{\c{c}}ois},
  booktitle={2012 IEEE 53rd annual symposium on foundations of computer science},
  pages={514--523},
  year={2012},
  organization={IEEE}
}

@article{fredman1975computing,
  title={On computing the length of longest increasing subsequences},
  author={Fredman, Michael L},
  journal={Discrete Mathematics},
  volume={11},
  number={1},
  pages={29--35},
  year={1975},
  publisher={Elsevier}
}

@article{hunt1977fast,
  title={A fast algorithm for computing longest common subsequences},
  author={Hunt, James W and Szymanski, Thomas G},
  journal={Communications of the ACM},
  volume={20},
  number={5},
  pages={350--353},
  year={1977},
  publisher={ACM}
}

@book{bengtsson2007computing,
  title={Computing maximum-scoring segments optimally},
  author={Bengtsson, Fredrik and Chen, Jingsen},
  year={2007},
  publisher={Lule{\aa} tekniska universitet}
}

@inproceedings{nederlof2012reducing,
  title={Reducing a target interval to a few exact queries},
  author={Nederlof, Jesper and van Leeuwen, Erik Jan and van der Zwaan, Ruben},
  booktitle={International Symposium on Mathematical Foundations of Computer Science},
  pages={718--727},
  year={2012},
  organization={Springer}
}

@article{frederickson2017optimal,
  title={Optimal Parametric Search for Path and Tree Partitioning},
  author={Frederickson, Greg N and Zhou, Samson},
  journal={arXiv preprint arXiv:1711.00599},
  year={2017}
}

@inproceedings{frederickson1991optimal,
  title={Optimal algorithms for tree partitioning},
  author={Frederickson, Greg N},
  booktitle={SODA},
  volume={91},
  pages={168--177},
  year={1991}
}

@article{kaplan2018selection,
  title={Selection from heaps, row-sorted matrices and ${X}+{Y}$ using soft heaps},
  author={Kaplan, Haim and Kozma, L{\'a}szl{\'o} and Zamir, Or and Zwick, Uri},
  journal={arXiv preprint arXiv:1802.07041},
  year={2018}
}

@article{verhoeff2004settling,
  title={Settling multiple debts efficiently: An invitation to computing science},
  author={Verhoeff, Tom and others},
  journal={Informatics in Education-An International Journal},
  volume={3},
  number={1},
  pages={105--126},
  year={2004},
  publisher={Vilniaus Universiteto Leidykla}
}

@article{rubinchik2018eertree,
  title={EERTREE: an efficient data structure for processing palindromes in strings},
  author={Rubinchik, Mikhail and Shur, Arseny M},
  journal={European Journal of Combinatorics},
  volume={68},
  pages={249--265},
  year={2018},
  publisher={Elsevier}
}

@article{fici2014subquadratic,
  title={A subquadratic algorithm for minimum palindromic factorization},
  author={Fici, Gabriele and Gagie, Travis and K{\"a}rkk{\"a}inen, Juha and Kempa, Dominik},
  journal={Journal of Discrete Algorithms},
  volume={28},
  pages={41--48},
  year={2014},
  publisher={Elsevier}
}

@inproceedings{durocher2011range,
  title={Range majority in constant time and linear space},
  author={Durocher, Stephane and He, Meng and Munro, J Ian and Nicholson, Patrick K and Skala, Matthew},
  booktitle={International Colloquium on Automata, Languages, and Programming},
  pages={244--255},
  year={2011},
  organization={Springer}
}

@inproceedings{yao1982space,
  title={Space-time tradeoff for answering range queries},
  author={Yao, Andrew C},
  booktitle={Proceedings of the fourteenth annual ACM symposium on Theory of computing},
  pages={128--136},
  year={1982},
  organization={ACM}
}

@book{alon1987optimal,
  title={Optimal preprocessing for answering on-line product queries},
  author={Alon, Noga and Schieber, Baruch},
  year={1987},
  publisher={Citeseer}
}

@inproceedings{beame1999optimal,
  title={Optimal bounds for the predecessor problem},
  author={Beame, Paul and Fich, Faith E},
  booktitle={STOC},
  volume={99},
  pages={295--304},
  year={1999},
  organization={Citeseer}
}

@inproceedings{patrascu2014dynamic,
  title={Dynamic integer sets with optimal rank, select, and predecessor search},
  author={P{\u{a}}tra{\c{s}}cu, Mihai and Thorup, Mikkel},
  booktitle={2014 IEEE 55th Annual Symposium on Foundations of Computer Science},
  pages={166--175},
  year={2014},
  organization={IEEE}
}

@article{navarro2016optimal,
  title={Optimal encodings for range majority queries},
  author={Navarro, Gonzalo and Thankachan, Sharma V},
  journal={Algorithmica},
  volume={74},
  number={3},
  pages={1082--1098},
  year={2016},
  publisher={Springer}
}

@article{kopelowitz2019strong,
  title={The Strong 3SUM-INDEXING Conjecture is False},
  author={Kopelowitz, Tsvi and Porat, Ely},
  journal={arXiv preprint arXiv:1907.11206},
  year={2019}
}

@inproceedings{Zhu2016An,
  title={An Optimal Algorithm for a Computer Game in Linear Time},
  author={Zhu, Daxin and Wang, Xiaodong},
  booktitle={International Conference on Smart Computing \& Communication},
  year={2016},
}

@inproceedings{bringmann2017dichotomy,
  title={A dichotomy for regular expression membership testing},
  author={Bringmann, Karl and Gr{\o}nlund, Allan and Larsen, Kasper Green},
  booktitle={2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)},
  pages={307--318},
  year={2017},
  organization={IEEE}
}

@article{alon1997finding,
  title={Finding and counting given length cycles},
  author={Alon, Noga and Yuster, Raphael and Zwick, Uri},
  journal={Algorithmica},
  volume={17},
  number={3},
  pages={209--223},
  year={1997},
  publisher={Springer}
}

@inproceedings{alon1994color,
  title={Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs},
  author={Alon, Noga and Yuster, Raphael and Zwick, Uri},
  booktitle={STOC},
  volume={94},
  pages={326--335},
  year={1994}
}

@article{keikha2017maximum,
  title={Maximum-area triangle in a convex polygon, revisited},
  author={Keikha, Vahideh and L{\"o}ffler, Maarten and Mohades, Ali and Urhausen, J{\'e}r{\^o}me and van der Hoog, Ivor},
  journal={arXiv preprint arXiv:1705.11035},
  year={2017}
}

@article{jin2017maximal,
  title={Maximal area triangles in a convex polygon},
  author={Jin, Kai},
  journal={arXiv preprint arXiv:1707.04071},
  year={2017}
}

@inproceedings{dobkin1979general,
  title={On a general method for maximizing and minimizing among certain geometric problems},
  author={Dobkin, David P and Snyder, Lawrence},
  booktitle={20th Annual Symposium on Foundations of Computer Science (sfcs 1979)},
  pages={9--17},
  year={1979},
  organization={IEEE}
}

@article{grabowski2016new,
  title={New tabulation and sparse dynamic programming based techniques for sequence similarity problems},
  author={Grabowski, Szymon},
  journal={Discrete Applied Mathematics},
  volume={212},
  pages={96--103},
  year={2016},
  publisher={Elsevier}
}

@inproceedings{chan2016deterministic,
  title={Deterministic APSP, orthogonal vectors, and more: Quickly derandomizing Razborov-Smolensky},
  author={Chan, Timothy M. and Williams, Ryan},
  booktitle={Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms},
  pages={1246--1255},
  year={2016},
  organization={Society for Industrial and Applied Mathematics}
}

@inproceedings{abboud2015more,
  title={More applications of the polynomial method to algorithm design},
  author={Abboud, Amir and Williams, Ryan and Yu, Huacheng},
  booktitle={Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms},
  pages={218--230},
  year={2015},
  organization={Society for Industrial and Applied Mathematics}
}

@inproceedings{afshani2017independent,
  title={Independent range sampling, revisited},
  author={Afshani, Peyman and Wei, Zhewei},
  booktitle={25th Annual European Symposium on Algorithms (ESA 2017)},
  year={2017},
  organization={Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik}
}

@article{afshani2019independent,
  title={Independent range sampling, revisited again},
  author={Afshani, Peyman and Phillips, Jeff M},
  journal={arXiv preprint arXiv:1903.08014},
  year={2019}
}

@article{erickson1999finding,
  title={Finding longest arithmetic progressions},
  author={Erickson, Je},
  year={1999},
  publisher={Citeseer}
}

@article{dudek2020all,
  title={All non-trivial variants of 3-LDT are equivalent},
  author={Dudek, Bart{\l}omiej and Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana},
  journal={arXiv preprint arXiv:2001.01289},
  year={2020}
}

@article{fredman1978complexity,
  title={On the complexity of computing the measure of $\cup$[ai, bi]},
  author={Fredman, Michael L and Weide, Bruce},
  journal={Communications of the ACM},
  volume={21},
  number={7},
  pages={540--544},
  year={1978},
  publisher={ACM}
}

@inproceedings{backurs2016regular,
  title={Which regular expression patterns are hard to match?},
  author={Backurs, Arturs and Indyk, Piotr},
  booktitle={2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)},
  pages={457--466},
  year={2016},
  organization={IEEE}
}

@inproceedings{chan2013klee,
  title={Klee's measure problem made easy},
  author={Chan, Timothy M.},
  booktitle={2013 IEEE 54th annual symposium on foundations of computer science},
  pages={410--419},
  year={2013},
  organization={IEEE}
}

@inproceedings{williams2014faster,
  title={Faster all-pairs shortest paths via circuit complexity},
  author={Williams, Ryan},
  booktitle={Proceedings of the forty-sixth annual ACM symposium on Theory of computing},
  pages={664--673},
  year={2014}
}

@inproceedings{chan2016deterministic,
  title={Deterministic apsp, orthogonal vectors, and more: Quickly derandomizing razborov-smolensky},
  author={Chan, Timothy M. and Williams, Ryan},
  booktitle={Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms},
  pages={1246--1255},
  year={2016},
  organization={SIAM}
}

@article{thorup1999undirected,
  title={Undirected single-source shortest paths with positive integer weights in linear time},
  author={Thorup, Mikkel},
  journal={Journal of the ACM (JACM)},
  volume={46},
  number={3},
  pages={362--394},
  year={1999},
  publisher={ACM New York, NY, USA}
}

@article{eppstein1995dynamic,
  title={Dynamic Euclidean minimum spanning trees and extrema of binary functions},
  author={Eppstein, David},
  journal={Discrete \& Computational Geometry},
  volume={13},
  number={1},
  pages={111--122},
  year={1995},
  publisher={Springer}
}

@inproceedings{chan2020dynamic,
  title={Dynamic Generalized Closest Pair: Revisiting Eppstein's Technique},
  author={Chan, Timothy M.},
  booktitle={Symposium on Simplicity in Algorithms},
  pages={33--37},
  year={2020},
  organization={SIAM}
}

@article{vaidya1989geometry,
  title={Geometry helps in matching},
  author={Vaidya, Pravin M},
  journal={SIAM Journal on Computing},
  volume={18},
  number={6},
  pages={1201--1225},
  year={1989},
  publisher={SIAM}
}

@article{agarwal2000vertical,
  title={Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications},
  author={Agarwal, Pankaj K and Efrat, Alon and Sharir, Micha},
  journal={SIAM Journal on Computing},
  volume={29},
  number={3},
  pages={912--953},
  year={2000},
  publisher={SIAM}
}

@article{karger1995randomized,
  title={A randomized linear-time algorithm to find minimum spanning trees},
  author={Karger, David R and Klein, Philip N and Tarjan, Robert E},
  journal={Journal of the ACM (JACM)},
  volume={42},
  number={2},
  pages={321--328},
  year={1995},
  publisher={ACM New York, NY, USA}
}

@inproceedings{alstrup2001optimal,
  title={Optimal static range reporting in one dimension},
  author={Alstrup, Stephen and Brodal, Gerth and Rauhe, Theis},
  booktitle={Proceedings of the thirty-third annual ACM symposium on Theory of computing},
  pages={476--482},
  year={2001}
}

@inproceedings{mortensen2005dynamic,
  title={On dynamic range reporting in one dimension},
  author={Mortensen, Christian Worm and Pagh, Rasmus and P{\u{a}}tra{\c{s}}cu, Mihai},
  booktitle={Proceedings of the thirty-seventh annual ACM symposium on Theory of computing},
  pages={104--111},
  year={2005}
}

@article{sladkey2012successive,
  title={A Successive Approximation Algorithm for Computing the Divisor Summatory Function},
  author={Sladkey, Richard},
  journal={arXiv preprint arXiv:1206.3369},
  year={2012}
}

@inproceedings{chan2020change,
  title={On the Change-Making Problem},
  author={Chan, Timothy M. and He, Qizheng},
  booktitle={Symposium on Simplicity in Algorithms},
  pages={38--42},
  year={2020},
  organization={SIAM}
}

@inproceedings{yuan2010data,
  title={Data structures for range minimum queries in multidimensional arrays},
  author={Yuan, Hao and Atallah, Mikhail J},
  booktitle={Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithms},
  pages={150--160},
  year={2010},
  organization={SIAM}
}

@inproceedings{golin2011encoding,
  title={Encoding 2D range maximum queries},
  author={Golin, Mordecai and Iacono, John and Krizanc, Danny and Raman, Rajeev and Rao, S Srinivasa},
  booktitle={International Symposium on Algorithms and Computation},
  pages={180--189},
  year={2011},
  organization={Springer}
}

@inproceedings{karczmarz2019min,
  title={Min-Cost Flow in Unit-Capacity Planar Graphs},
  author={Karczmarz, Adam and Sankowski, Piotr},
  booktitle={27th Annual European Symposium on Algorithms (ESA 2019)},
  year={2019}
}

@inproceedings{mozes2010shortest,
  title={Shortest paths in planar graphs with real lengths in ${O}(n\log^2 n/\log\log n)$ time},
  author={Mozes, Shay and Wulff-Nilsen, Christian},
  booktitle={European Symposium on Algorithms},
  pages={206--217},
  year={2010},
  organization={Springer}
}

@article{mirzaian1985selection,
  title={Selection in X+ Y and matrices with sorted rows and columns},
  author={Mirzaian, Andranik and Arjomandi, Eshrat},
  journal={Information processing letters},
  volume={20},
  number={1},
  pages={13--17},
  year={1985},
  publisher={Elsevier}
}

@article{gabow1985linear,
  title={A linear-time algorithm for a special case of disjoint set union},
  author={Gabow, Harold N and Tarjan, Robert Endre},
  journal={Journal of computer and system sciences},
  volume={30},
  number={2},
  pages={209--221},
  year={1985},
  publisher={Elsevier}
}

@article{kwok1999static,
  title={Static scheduling algorithms for allocating directed task graphs to multiprocessors},
  author={Kwok, Yu-Kwong and Ahmad, Ishfaq},
  journal={ACM Computing Surveys (CSUR)},
  volume={31},
  number={4},
  pages={406--471},
  year={1999},
  publisher={ACM New York, NY, USA}
}

@article{ullman1975np,
  title={NP-complete scheduling problems},
  author={Ullman, Jeffrey D.},
  journal={Journal of Computer and System sciences},
  volume={10},
  number={3},
  pages={384--393},
  year={1975},
  publisher={Academic Press}
}

@article{gronlund2017fast,
  title={Fast exact k-means, k-medians and bregman divergence clustering in 1d},
  author={Gr{\o}nlund, Allan and Larsen, Kasper Green and Mathiasen, Alexander and Nielsen, Jesper Sindahl and Schneider, Stefan and Song, Mingzhou},
  journal={arXiv preprint arXiv:1701.07204},
  year={2017}
}

@article{wang2016line,
  title={Line-constrained k-median, k-means, and k-center problems in the plane},
  author={Wang, Haitao and Zhang, Jingru},
  journal={International Journal of Computational Geometry \& Applications},
  volume={26},
  number={3-4},
  pages={185--210},
  year={2016},
  publisher={World Scientific}
}

@book{knuth2011art,
  title={The art of computer programming, volume 4A: combinatorial algorithms, part 1},
  author={Knuth, Donald E},
  year={2011},
  publisher={Pearson Education India}
}

@article{har2005fast,
  title={Fast algorithms for computing the smallest k-enclosing circle},
  author={Har-Peled, Sariel and Mazumdar, Soham},
  journal={Algorithmica},
  volume={41},
  number={3},
  pages={147--157},
  year={2005},
  publisher={Springer}
}

@article{efrat1994computing,
  title={Computing the smallest k-enclosing circle and related problems},
  author={Efrat, Alon and Sharir, Micha and Ziv, Alon},
  journal={Computational Geometry},
  volume={4},
  number={3},
  pages={119--136},
  year={1994},
  publisher={Elsevier}
}

@article{van1991finding,
  title={Finding squares and rectangles in sets of points},
  author={Van Kreveld, Marc J and De Berg, Mark T},
  journal={BIT Numerical Mathematics},
  volume={31},
  number={2},
  pages={202--219},
  year={1991},
  publisher={Springer}
}

@article{walters2009rectangles,
  title={Rectangles as sums of squares},
  author={Walters, Mark},
  journal={Discrete mathematics},
  volume={309},
  number={9},
  pages={2913--2921},
  year={2009},
  publisher={Elsevier}
}

@article{han2020sorting,
  title={Sorting Real Numbers in ${O}(n\sqrt{\log n})$ Time and Linear Space},
  author={Han, Yijie},
  journal={Algorithmica},
  volume={82},
  number={4},
  pages={966--978},
  year={2020},
  publisher={Springer}
}

@inproceedings{cohen2016geometric,
  title={Geometric median in nearly linear time},
  author={Cohen, Michael B and Lee, Yin Tat and Miller, Gary and Pachocki, Jakub and Sidford, Aaron},
  booktitle={Proceedings of the forty-eighth annual ACM symposium on Theory of Computing},
  pages={9--21},
  year={2016}
}

@article{weiszfeld1937point,
  title={Sur le point pour lequel la somme des distances de n points donn{\'e}s est minimum},
  author={Weiszfeld, Endre},
  journal={Tohoku Mathematical Journal, First Series},
  volume={43},
  pages={355--386},
  year={1937},
  publisher={Mathematical Institute, Tohoku University}
}

@article{gusfield1997algorithms,
  title={Algorithms on strings, trees, and sequences: Computer science and computational biology},
  author={Gusfield, Dan},
  journal={Acm Sigact News},
  volume={28},
  number={4},
  pages={41--60},
  year={1997},
  publisher={ACM New York, NY, USA}
}

@inproceedings{chi1992color,
  title={Color set size problem with applications to string matching},
  author={Chi, Lucas and Hui, Kwong},
  booktitle={Annual Symposium on Combinatorial Pattern Matching},
  pages={230--243},
  year={1992},
  organization={Springer}
}

@article{atkin2004prime,
  title={Prime sieves using binary quadratic forms},
  author={Atkin, Arthur and Bernstein, Daniel},
  journal={Mathematics of Computation},
  volume={73},
  number={246},
  pages={1023--1030},
  year={2004}
}

@article{pritchard1982explaining,
  title={Explaining the Wheel Sieve},
  author={Pritchard, Paul},
  journal={Acta Informatica},
  volume={17},
  pages={477--485},
  year={1982},
  publisher={Springer}
}

@inproceedings{DBLP:conf/stacs/LackiS15,
  author    = {Jakub Lacki and
               Piotr Sankowski},
  editor    = {Ernst W. Mayr and
               Nicolas Ollinger},
  title     = {Optimal Decremental Connectivity in Planar Graphs},
  booktitle = {32nd International Symposium on Theoretical Aspects of Computer Science,
               {STACS} 2015, March 4-7, 2015, Garching, Germany},
  series    = {LIPIcs},
  volume    = {30},
  pages     = {608--621},
  !publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year      = {2015},
  url       = {https://doi.org/10.4230/LIPIcs.STACS.2015.608},
  doi       = {10.4230/LIPIcs.STACS.2015.608},
  timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
  biburl    = {https://dblp.org/rec/conf/stacs/LackiS15.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{gustedt1998efficient,
  title={Efficient union-find for planar graphs and other sparse graph classes},
  author={Gustedt, Jens},
  journal={Theoretical Computer Science},
  volume={203},
  number={1},
  pages={123--141},
  year={1998},
  publisher={Elsevier}
}

@inproceedings{chan2020more,
  title={More on Change-Making and Related Problems},
  author={Chan, Timothy M. and He, Qizheng},
  booktitle={28th Annual European Symposium on Algorithms (ESA)},
  year={2020}
}

@article{axiotis2020fast,
  title={Fast and Simple Modular Subset Sum},
  author={Axiotis, Kyriakos and Backurs, Arturs and Bringmann, Karl and Jin, Ce and Nakos, Vasileios and Tzamos, Christos and Wu, Hongxun},
  journal={arXiv preprint arXiv:2008.10577},
  year={2020}
}

@article{goldwasser2005linear,
  title={Linear-time algorithms for computing maximum-density sequence segments with bioinformatics applications},
  author={Goldwasser, Michael H and Kao, Ming-Yang and Lu, Hsueh-I},
  journal={Journal of Computer and System Sciences},
  volume={70},
  number={2},
  pages={128--144},
  year={2005},
  publisher={Elsevier}
}

@article{van2020bipartite,
  title={Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs},
  author={van den Brand, Jan and Lee, Yin-Tat and Nanongkai, Danupon and Peng, Richard and Saranurak, Thatchaphol and Sidford, Aaron and Song, Zhao and Wang, Di},
  journal={arXiv e-prints},
  pages={arXiv--2009},
  year={2020}
}

@inproceedings{cohen2017negative,
  title={Negative-weight shortest paths and unit capacity minimum cost flow in $\tilde{O}(m^{10/7} \log {W})$ time},
  author={Cohen, Michael B and Madry, Aleksander and Sankowski, Piotr and Vladu, Adrian},
  booktitle={Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms},
  pages={752--771},
  year={2017},
  organization={SIAM}
}

@article{gabow1989faster,
  title={Faster scaling algorithms for network problems},
  author={Gabow, Harold N and Tarjan, Robert E},
  journal={SIAM Journal on Computing},
  volume={18},
  number={5},
  pages={1013--1036},
  year={1989},
  publisher={SIAM}
}

@article{axiotis2020circulation,
  title={Circulation control for faster minimum cost flow in unit-capacity graphs},
  author={Axiotis, Kyriakos and Madry, Aleksander and Vladu, Adrian},
  journal={arXiv preprint arXiv:2003.04863},
  year={2020}
}

@inproceedings{rahman2006finding,
  title={Finding patterns with variable length gaps or don’t cares},
  author={Rahman, M Sohel and Iliopoulos, Costas S and Lee, Inbok and Mohamed, Manal and Smyth, William F},
  booktitle={International Computing and Combinatorics Conference},
  pages={146--155},
  year={2006},
  organization={Springer}
}

@article{bille2012string,
  title={String matching with variable length gaps},
  author={Bille, Philip and G{\o}rtz, Inge Li and Vildh{\o}j, Hjalte Wedel and Wind, David Kofoed},
  journal={Theoretical Computer Science},
  volume={443},
  pages={25--34},
  year={2012},
  publisher={Elsevier}
}

@inproceedings{coppersmith2002almost,
  title={Almost optimal hash sequence traversal},
  author={Coppersmith, Don and Jakobsson, Markus},
  booktitle={International Conference on Financial Cryptography},
  pages={102--119},
  year={2002},
  organization={Springer}
}

@inproceedings{demaine2009cartesian,
  title={On cartesian trees and range minimum queries},
  author={Demaine, Erik D and Landau, Gad M and Weimann, Oren},
  booktitle={International Colloquium on Automata, Languages, and Programming},
  pages={341--353},
  year={2009},
  organization={Springer}
}

@inproceedings{chan2014succinct,
  title={Succinct indices for path minimum, with applications to path reporting},
  author={Chan, Timothy M. and He, Meng and Munro, J Ian and Zhou, Gelin},
  booktitle={European Symposium on Algorithms},
  pages={247--259},
  year={2014},
  organization={Springer}
}

@article{bjorklund2014determinant,
  title={Determinant sums for undirected hamiltonicity},
  author={Bjorklund, Andreas},
  journal={SIAM Journal on Computing},
  volume={43},
  number={1},
  pages={280--299},
  year={2014},
  publisher={SIAM}
}

@article{asathulla2019faster,
  title={A faster algorithm for minimum-cost bipartite perfect matching in planar graphs},
  author={Asathulla, Mudabir Kabir and Khanna, Sanjeev and Lahn, Nathaniel and Raghvendra, Sharath},
  journal={ACM Transactions on Algorithms (TALG)},
  volume={16},
  number={1},
  pages={1--30},
  year={2019},
  publisher={ACM New York, NY, USA}
}

@article{thorup2004integer,
  title={Integer priority queues with decrease key in constant time and the single source shortest paths problem},
  author={Thorup, Mikkel},
  journal={Journal of Computer and System Sciences},
  volume={69},
  number={3},
  pages={330--353},
  year={2004},
  publisher={Elsevier}
}

@inproceedings{chen2011efficient,
  title={Efficient algorithms for the weighted k-center problem on a real line},
  author={Chen, Danny Z and Wang, Haitao},
  booktitle={International Symposium on Algorithms and Computation},
  pages={584--593},
  year={2011},
  organization={Springer}
}

@inproceedings{frederickson1991parametric,
  title={Parametric search and locating supply centers in trees},
  author={Frederickson, Greg N},
  booktitle={Workshop on Algorithms and Data Structures},
  pages={299--319},
  year={1991},
  organization={Springer}
}

@article{lee1980two,
  title={Two-dimensional Voronoi diagrams in the Lp-metric},
  author={Lee, Der-Tsai},
  journal={Journal of the ACM (JACM)},
  volume={27},
  number={4},
  pages={604--618},
  year={1980},
  publisher={ACM New York, NY, USA}
}

@inproceedings{chan2018dynamic,
  title={Dynamic planar orthogonal point location in sublogarithmic time},
  author={Chan, Timothy M. and Tsakalidis, Konstantinos},
  booktitle={34th International Symposium on Computational Geometry (SoCG 2018)},
  year={2018},
  organization={Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik}
}

@inproceedings{nederlof2021faster,
  title={A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics},
  author={Nederlof, Jesper and Pawlewicz, Jakub and Swennenhuis, C{\'e}line MF and W{\k{e}}grzycki, Karol},
  booktitle={Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)},
  pages={1682--1701},
  year={2021},
  organization={SIAM}
}

@article{myrvold2001ranking,
  title={Ranking and unranking permutations in linear time},
  author={Myrvold, Wendy and Ruskey, Frank},
  journal={Information Processing Letters},
  volume={79},
  number={6},
  pages={281--284},
  year={2001},
  publisher={Elsevier}
}

@inproceedings{marevs2007linear,
  title={Linear-time ranking of permutations},
  author={Mare{\v{s}}, Martin and Straka, Milan},
  booktitle={European Symposium on Algorithms},
  pages={187--193},
  year={2007},
  organization={Springer}
}

@inproceedings{thorup2019dynamic,
  title={Dynamic ordered sets with approximate queries, approximate heaps and soft heaps},
  author={Thorup, Mikkel and Zamir, Or and Zwick, Uri},
  booktitle={46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  year={2019},
  organization={Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik}
}

@article{andersson2007dynamic,
  title={Dynamic ordered sets with exponential search trees},
  author={Andersson, Arne and Thorup, Mikkel},
  journal={Journal of the ACM (JACM)},
  volume={54},
  number={3},
  pages={13--es},
  year={2007},
  publisher={ACM New York, NY, USA}
}

@inproceedings{dietz1989fully,
  title={Fully persistent arrays},
  author={Dietz, Paul F},
  booktitle={Workshop on Algorithms and Data Structures},
  pages={67--74},
  year={1989},
  organization={Springer}
}

@inproceedings{okasaki1995purely,
  title={Purely functional random-access lists},
  author={Okasaki, Chris},
  booktitle={Proceedings of the seventh international conference on Functional programming languages and computer architecture},
  pages={86--95},
  year={1995}
}

@inproceedings{bringmann2021near,
  title={On Near-Linear-Time Algorithms for Dense Subset Sum},
  author={Bringmann, Karl and Wellnitz, Philip},
  booktitle={Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)},
  pages={1777--1796},
  year={2021},
  organization={SIAM}
}

@inproceedings{bostan2021simple,
  title={A Simple and Fast Algorithm for Computing the N-th Term of a Linearly Recurrent Sequence},
  author={Bostan, Alin and Mori, Ryuhei},
  booktitle={Symposium on Simplicity in Algorithms (SOSA)},
  pages={118--132},
  year={2021},
  organization={SIAM}
}

@inproceedings{italiano1991fully,
  title={Fully persistent data structures for disjoint set union problems},
  author={Italiano, Giuseppe F and Sarnak, Neil},
  booktitle={Workshop on Algorithms and Data Structures},
  pages={449--460},
  year={1991},
  organization={Springer}
}

@inproceedings{amir2007cost,
  title={On the cost of interchange rearrangement in strings},
  author={Amir, Amihood and Hartman, Tzvika and Kapah, Oren and Levy, Avivit and Porat, Ely},
  booktitle={European Symposium on Algorithms},
  pages={99--110},
  year={2007},
  organization={Springer}
}

@article{itai1978finding,
  title={Finding a minimum circuit in a graph},
  author={Itai, Alon and Rodeh, Michael},
  journal={SIAM Journal on Computing},
  volume={7},
  number={4},
  pages={413--423},
  year={1978},
  publisher={SIAM}
}

@inproceedings{williams2010subcubic,
  title={Subcubic equivalences between path, matrix and triangle problems},
  author={Williams, Virginia Vassilevska and Williams, Ryan},
  booktitle={2010 IEEE 51st Annual Symposium on Foundations of Computer Science},
  pages={645--654},
  year={2010},
  organization={IEEE}
}

@article{chan2010more,
  title={More algorithms for all-pairs shortest paths in weighted graphs},
  author={Chan, Timothy M.},
  journal={SIAM Journal on Computing},
  volume={39},
  number={5},
  pages={2075--2089},
  year={2010},
  publisher={SIAM}
}

@inproceedings{vassilevska2009finding,
  title={Finding, minimizing, and counting weighted subgraphs},
  author={Vassilevska, Virginia and Williams, Ryan},
  booktitle={Proceedings of the forty-first annual ACM symposium on Theory of computing},
  pages={455--464},
  year={2009}
}

@inproceedings{czumaj2007finding,
  title={Finding a heaviest triangle is not harder than matrix multiplication},
  author={Czumaj, Artur and Lingas, Andrzej},
  booktitle={Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms},
  pages={986--994},
  year={2007}
}

@article{czumaj2005improved,
  title={Improved algorithms for the all-pairs lowest common ancestor problem in directed acyclic graphs},
  author={Czumaj, Artur and Lingas, Andrzej},
  journal={Manuscript},
  year={2005}
}

@article{czumaj2007faster,
  title={Faster algorithms for finding lowest common ancestors in directed acyclic graphs},
  author={Czumaj, Artur and Kowaluk, Miros{\l}aw and Lingas, Andrzej},
  journal={Theoretical Computer Science},
  volume={380},
  number={1-2},
  pages={37--46},
  year={2007},
  publisher={Elsevier}
}

@inproceedings{cheng2014linear,
  title={Linear-time algorithms for proportional apportionment},
  author={Cheng, Zhanpeng and Eppstein, David},
  booktitle={International Symposium on Algorithms and Computation},
  pages={581--592},
  year={2014},
  organization={Springer}
}

@inproceedings{kosolobov2015pal,
  title={Pal k is linear recognizable online},
  author={Kosolobov, Dmitry and Rubinchik, Mikhail and Shur, Arseny M},
  booktitle={International Conference on Current Trends in Theory and Practice of Informatics},
  pages={289--301},
  year={2015},
  organization={Springer}
}

@article{rubinchik2020palindromic,
  title={Palindromic k-factorization in pure linear time},
  author={Rubinchik, Mikhail and Shur, Arseny M},
  journal={arXiv preprint arXiv:2002.03965},
  year={2020}
}

@inproceedings{borozdin2017palindromic,
  title={Palindromic length in linear time},
  author={Borozdin, Kirill and Kosolobov, Dmitry and Rubinchik, Mikhail and Shur, Arseny M},
  booktitle={28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)},
  year={2017},
  !organization={Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik}
}

@inproceedings{backurs2016tight,
  title={Tight Hardness Results for Maximum Weight Rectangles},
  author={Backurs, Arturs and Dikkala, Nishanth and Tzamos, Christos},
  booktitle={43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  year={2016},
  !organization={Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik}
}

@article{takaoka2002efficient,
  title={Efficient algorithms for the maximum subarray problem by distance matrix multiplication},
  author={Takaoka, Tadao},
  journal={Electronic Notes in Theoretical Computer Science},
  volume={61},
  pages={191--200},
  year={2002},
  publisher={Elsevier}
}

@article{chan1999geometric,
  title={Geometric applications of a randomized optimization technique},
  author={Chan, Timothy M},
  journal={Discrete \& Computational Geometry},
  volume={22},
  number={4},
  pages={547--567},
  year={1999},
  publisher={Springer}
}

@article{gabow1991faster,
  title={Faster scaling algorithms for general graph matching problems},
  author={Gabow, Harold N and Tarjan, Robert E},
  journal={Journal of the ACM (JACM)},
  volume={38},
  number={4},
  pages={815--853},
  year={1991},
  publisher={ACM New York, NY, USA}
}

@article{matouvsek1992efficient,
  title={Efficient partition trees},
  author={Matou{\v{s}}ek, Ji{\v{r}}{\'\i}},
  journal={Discrete \& Computational Geometry},
  volume={8},
  number={3},
  pages={315--334},
  year={1992},
  publisher={Springer}
}

@article{chazelle1989quasi,
  title={Quasi-optimal range searching in spaces of finite VC-dimension},
  author={Chazelle, Bernard and Welzl, Emo},
  journal={Discrete \& Computational Geometry},
  volume={4},
  number={5},
  pages={467--489},
  year={1989},
  publisher={Springer}
}

@article{valiant1979complexity,
  title={The complexity of enumeration and reliability problems},
  author={Valiant, Leslie G},
  journal={SIAM Journal on Computing},
  volume={8},
  number={3},
  pages={410--421},
  year={1979},
  publisher={SIAM}
}

@article{henzinger1997faster,
  title={Faster shortest-path algorithms for planar graphs},
  author={Henzinger, Monika R and Klein, Philip and Rao, Satish and Subramanian, Sairam},
  journal={journal of computer and system sciences},
  volume={55},
  number={1},
  pages={3--23},
  year={1997},
  publisher={Elsevier}
}

@inproceedings{dudek2020all,
  title={All non-trivial variants of 3-LDT are equivalent},
  author={Dudek, Bart{\l}omiej and Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana},
  booktitle={Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing},
  pages={974--981},
  year={2020}
}





